// Copyright [2022] <Tianyu Zhu, Shizhen Zhao, Zihang Ren>

#include <algorithm>
#include <cstdlib> // Header file needed to use srand and rand
#include <iostream>
#include <iomanip>
#include <fstream>
#include <stack>
#include <unordered_map>
#include <unistd.h>

#include "srlg_pulse.h"

// namespace
// {
//     void mem_usage(double &vm_usage, double &resident_set)
//     {
//         vm_usage = 0.0;
//         resident_set = 0.0;
//         std::ifstream stat_stream("/proc/self/stat", std::ios_base::in); // get info from proc directory
//         // create some variables to get info
//         std::string pid, comm, state, ppid, pgrp, session, tty_nr;
//         std::string tpgid, flags, minflt, cminflt, majflt, cmajflt;
//         std::string utime, stime, cutime, cstime, priority, nice;
//         std::string O, itrealvalue, starttime;
//         unsigned long vsize;
//         long rss;
//         stat_stream >> pid >> comm >> state >> ppid >> pgrp >> session >> tty_nr >> tpgid >> flags >> minflt >> cminflt >> majflt >> cmajflt >> utime >> stime >> cutime >> cstime >> priority >> nice >> O >> itrealvalue >> starttime >> vsize >> rss; // don't care about the rest
//         stat_stream.close();
//         long page_size_kb = sysconf(_SC_PAGE_SIZE) / 1024; // for x86-64 is configured to use 2MB pages
//         vm_usage = vsize / 1024.0;
//         resident_set = rss * page_size_kb;
//     }

// } // namespace

SrlgPulse::~SrlgPulse()
{
    if (dst_cost_map_)
    {
        delete[] dst_cost_map_;
        dst_cost_map_ = nullptr;
    }
    if (dst_delay_map_)
    {
        delete[] dst_delay_map_;
        dst_delay_map_ = nullptr;
    }
    if (src_visited_)
    {
        delete[] src_visited_;
        src_visited_ = nullptr;
    }
    if (bp_visited_)
    {
        delete[] bp_visited_;
        bp_visited_ = nullptr;
    }

    if (info_)
    {
        delete[] info_;
        info_ = nullptr;
    }
}

void SrlgPulse::SetupTopology(Graph *graph)
{
    graph_ = graph;
    num_nodes_ = graph_->NodeSize();
    dst_cost_map_ = new double[num_nodes_];
    dst_delay_map_ = new double[num_nodes_];
    src_visited_ = new bool[num_nodes_];
    bp_visited_ = new bool[num_nodes_];
    info_ = new PulseInfo[num_nodes_]();
}

void SrlgPulse::SortLinks()
{
    for (Link &link : graph_->GetMutableLinks())
    {
        link.weight = link.delay + dst_delay_map_[link.ter_id];
    }
    graph_->SortLinks();
}

Path SrlgPulse::FindPath(const Flow &flow)
{
    // Initialization
    // do dijkstra from end to every other nodes,
    // from two perspectives--cost and delay
    // store the result of dijkstras in cost_map and delay_map
    flow_ = flow;
    start_time_ = clock();
    DstDijkstra(flow_.to, false, dst_cost_map_);
    DstDijkstra(flow_.to, true, dst_delay_map_);
    SortLinks();

    end_time_ = clock();
    std::cout << "Pulse initialization time: "
              << double(end_time_ - start_time_) / CLOCKS_PER_SEC * 1000
              << "(ms).\n";
    std::cout << "Optimal cost: " << dst_cost_map_[flow_.from]
              << ", Optimal delay: " << dst_delay_map_[flow_.from] << ".\n";

    // Reset Pulse Algorithm
    for (int i = 0; i < num_nodes_; ++i)
    {
        src_visited_[i] = false;
        info_[i].Clear();
    }
    total_cost_ = kMaxValue;
    results_.clear();
    time_ms_cost_pairs_.clear();
    // Timer starts
    start_time_ = clock();
    // Start pulse algorithm
    Dfs();

    // Print time elapse
    end_time_ = clock();
    std::cout << "Pulse time: "
              << double(end_time_ - start_time_) / CLOCKS_PER_SEC * 1000
              << "(ms).\n\n";
    // double vm;
    // double rss;
    // mem_usage(vm, rss);
    // std::cout << "Virtual Memory Usage:  " << vm / 1024 << " (MB)" << std::endl;
    // std::cout << "Resident Set Usage:    " << vm / 1024 << " (MB)" << std::endl;
    return results_;
}

PathPair SrlgPulse::FindPathPair(const Flow &flow)
{
    // Initialization
    // do dijkstra from end to every other nodes,
    // from two perspectives--cost and delay
    // store the result of dijkstras in cost_map and delay_map
    flow_ = flow;
    start_time_ = clock();
    DstDijkstra(flow_.to, false, dst_cost_map_);
    DstDijkstra(flow_.to, true, dst_delay_map_);
    SortLinks();

    end_time_ = clock();

    std::cout << "Pulse initialization time: "
              << double(end_time_ - start_time_) / CLOCKS_PER_SEC * 1000
              << "(ms).\n";
    std::cout << "Optimal cost: " << dst_cost_map_[flow_.from]
              << ", Optimal delay: " << dst_delay_map_[flow_.from] << ".\n";

    // Reset Pulse Algorithm
    for (int i = 0; i < num_nodes_; ++i)
    {
        src_visited_[i] = false;
        bp_visited_[i] = false;
        info_[i].Clear();
    }
    total_cost_ = kMaxValue;
    time_ms_cost_pairs_.clear();
    path_pair_.clear();
    // Timer starts
    start_time_ = clock();
    // Start pulse algorithm
    APDfs(flow.type);
    // Print time elapse
    end_time_ = clock();
    // double vm;
    // double rss;
    // mem_usage(vm, rss);
    std::cout << "Pulse time: "
              << double(end_time_ - start_time_) / CLOCKS_PER_SEC * 1000
              << "(ms).\n\n";
    // std::cout << "Virtual Memory Usage:  \033[33m" << vm / 1024 << "\033[0m\033[36m (MB)\033[0m" << std::endl;
    // std::cout << "Resident Set Usage:    \033[33m" << vm / 1024 << "\033[0m\033[36m (MB)\033[0m" << std::endl;
    return path_pair_;
}

// dijkstra algorithm
// if(flag == false)--search according to cost
// if(flag == true)--search according to delay
void SrlgPulse::DstDijkstra(
    NodeId dst_node, bool flag, double *node_to_dst_dis)
{
    for (int i = 0; i < num_nodes_; ++i)
    {
        node_to_dst_dis[i] = kMaxValue;
    }
    node_to_dst_dis[dst_node] = 0;
    std::priority_queue<Node<NodeId>, std::vector<Node<NodeId>>> heap;
    std::vector<bool> visited(num_nodes_, false);
    heap.push(Node<NodeId>(dst_node, 0));
    int size = visited.size();
    // int s =
    while (!heap.empty())
    {
        NodeId u = heap.top().id;
        double weight_u_to_dst = heap.top().distance;
        heap.pop();
        if (visited[u])
            continue;
        visited[u] = true;
        for (Link *link : graph_->GetIngressLinks(u))
        {
            NodeId v = link->source_id;
            if (visited[v])
                continue;
            double weight = flag ? link->delay : link->cost;
            if (node_to_dst_dis[v] > weight_u_to_dst + weight)
            {
                node_to_dst_dis[v] = weight_u_to_dst + weight;
                heap.push(Node<NodeId>(v, node_to_dst_dis[v]));
            }
        }
    }
}

// update the path node U records
// according to the rule mentioned in Chapter 4 of 2012.10 paper
bool SrlgPulse::updateSrcPath(NodeId u, double cost, double delay)
{
    if (info_[u].src_delay_to_cost_map[delay] <= cost)
    {
        return false;
    }
    info_[u].src_delay_to_cost_map[delay] = cost;
    return true;
}

// dfs from start to end, use recursion

void SrlgPulse::Dfs()
{
    struct Snapshot
    {
        NodeId node;
        double cost;
        double delay;
        int stage;
    };
    std::vector<Snapshot> src_stack;
    src_stack.reserve(1000000);
    Path src_path;
    src_path.path_info = {};
    src_path.cost = 0;
    src_path.delay = 0;
    Snapshot snapshot;
    snapshot.node = flow_.from;
    snapshot.cost = 0;
    snapshot.delay = 0;
    snapshot.stage = 0;
    src_stack.push_back(snapshot);
    int num_iterations = 0;
    while (!src_stack.empty())
    {
        ++num_iterations;
        Snapshot src_snap = src_stack.back();
        src_stack.pop_back();
        NodeId u = src_snap.node;
        if (src_snap.stage == 1)
        {
            src_path.path_info.pop_back();
            src_path.cost -= src_snap.cost;
            src_path.delay -= src_snap.delay;
            src_visited_[u] = false;
        }
        else
        {
            double path_cost = src_path.cost + src_snap.cost;
            double path_delay = src_path.delay + src_snap.delay;
            if (u == flow_.to)
            {
                // src_path.Print();
                if (path_delay <= flow_.delay_ub &&
                    path_delay >= flow_.delay_lb &&
                    path_cost < total_cost_)
                {
                    total_cost_ = path_cost;
                    results_ = src_path;
                    results_.path_info.push_back(u);
                    results_.cost = path_cost;
                    results_.delay = path_delay;
                    end_time_ = clock();
                    time_ms_cost_pairs_.emplace_back(
                        static_cast<double>(end_time_ - start_time_) /
                            CLOCKS_PER_SEC * 1000,
                        path_cost);
                }
            }
            else
            {
                // prune
                if (dst_cost_map_[u] + path_cost < total_cost_ &&
                    dst_delay_map_[u] + path_delay <= flow_.delay_ub &&
                    (accurate_ || updateSrcPath(u, path_cost, path_delay)))
                {
                    const std::vector<Link *> &egress_links =
                        graph_->GetEgressLinks(u);
                    if (!egress_links.empty())
                    {
                        src_path.path_info.push_back(u);
                        src_path.cost = path_cost;
                        src_path.delay = path_delay;
                        src_visited_[u] = true;
                        src_snap.stage = 1;
                        src_stack.push_back(src_snap);
                        for (Link *link : egress_links)
                        {
                            NodeId node_id = link->ter_id;
                            if (src_visited_[node_id])
                            {
                                continue;
                            }
                            Snapshot snap;
                            snap.node = node_id;
                            snap.delay = link->delay;
                            snap.cost = link->cost;
                            snap.stage = 0;
                            src_stack.push_back(snap);
                        }
                    }
                }
            }
        }
    }
    std::cout << "Total number of iterations: " << num_iterations << "\n";
}

int SrlgPulse::find_link_in_conflict_path(Link *link)
{
    for (Link *conflict_link : conflict_set_.path_link)
    {
        if (link == conflict_link)
            return 1;
    }
    return 0;
}
// TODO cost 和 delay在含有conflict link时候的减值有问题
void SrlgPulse::APDfs(int type)
{
    struct Snapshot
    {
        NodeId node;
        Link *link;
        double cost;
        double delay;
        int stage;
        int cnt;
    };
    
    std::vector<Snapshot> src_stack;
    src_stack.reserve(1000000);
    Path src_path;
    src_path.path_info = {};
    src_path.path_link = {};

    src_path.cost = 0;
    src_path.delay = 0;
    Snapshot snapshot;
    snapshot.node = flow_.from;
    snapshot.cost = 0;
    snapshot.delay = 0;
    snapshot.stage = 0;
    snapshot.link = nullptr;
    src_stack.push_back(snapshot);
    int num_iterations = 0;
    int total_conflict_num = 0;
    Path ap;
    // int num = 0;
    // std::vector<int> useless_nodes;
    while (!src_stack.empty())
    {
        ++num_iterations;
        Snapshot src_snap = src_stack.back();
        src_stack.pop_back();
        NodeId u = src_snap.node;
        // std::cout << "Total number of iterations: " << num_iterations << "\n";
        // std::cout << ++num << std::endl;

        if (src_snap.stage == 1)
        {
            src_path.path_info.pop_back();
            src_path.cost -= src_snap.cost;
            src_path.delay -= src_snap.delay;
            total_conflict_num -= src_snap.cnt;
            src_visited_[u] = false;
            src_path.path_link.pop_back();
        }
        else
        {
            double path_cost = src_path.cost + src_snap.cost;
            double path_delay = src_path.delay + src_snap.delay;
            if (u == flow_.to)
            {
                // src_path.Print();
                // std::cout << "Total number of iterations: " << num_iterations << "\n";
                if (path_delay <= flow_.delay_ub &&
                    path_delay >= flow_.delay_lb &&
                    path_cost < total_cost_)
                {  
                    Flow flow_buffer = flow_;
                    Path tmp = src_path;
                    tmp.path_link.emplace_back(src_snap.link);
                    tmp.cost = path_cost;
                    tmp.delay = path_delay;
                    Path bp;
                    conflict_set_.clear();
                    total_conflict_num = 0;
                    if (type == 0)
                        bp = LinkSep(tmp);
                    else if (type == 1)
                        bp = NodeSep(tmp);
                    else
                        bp = SrlgSep(tmp);
                    flow_ = flow_buffer;
                    Path conflict_set_buffer = conflict_set_;
                    if (bp.cost == kMaxValue)
                    {
                        // if (bp.delay != kMaxDelay)
                        //     useless_nodes.push_back(bp.delay);
                        for (Link *link : conflict_set_buffer.path_link)
                        {
                            link->used = false;
                        }

                        for (Link *link : conflict_set_.path_link)
                        {
                            link->used = true;
                        }

                        for (int i = 0; i < src_stack.size(); ++i)
                        {
                            src_stack[i].cnt = find_link_in_conflict_path(src_stack[i].link);
                            total_conflict_num += src_stack[i].cnt;
                        }

                        continue;
                    }
                    for (int i = 0; i < src_stack.size(); ++i)
                    {
                        src_stack[i].cnt = 0;
                    }
                    ap = tmp;
                    ap.path_info.push_back(u);
                    if (bp.cost < ap.cost)
                    {
                        Path buffer = ap;
                        ap = bp;
                        bp = buffer;
                    }
                    total_cost_ = ap.cost;
                    path_pair_.ap_path = ap;
                    path_pair_.bp_path = bp;
                    end_time_ = clock();
                    time_ms_cost_pairs_.emplace_back(
                        static_cast<double>(end_time_ - start_time_) /
                            CLOCKS_PER_SEC * 1000,
                        path_cost);
                }
            }
            else
            {
                // prune
                if (dst_cost_map_[u] + path_cost < total_cost_ &&
                    dst_delay_map_[u] + path_delay <= flow_.delay_ub &&
                    (accurate_ || updateSrcPath(u, path_cost, path_delay)))
                {
                    const std::vector<Link *> &egress_links =
                        graph_->GetEgressLinks(u);
                    if (!egress_links.empty())
                    {
                        if (conflict_set_.path_link.size() != 0 && total_conflict_num + src_snap.cnt == conflict_set_.path_link.size())
                            continue;
                        src_path.path_info.push_back(u);
                        if (src_snap.link != nullptr)
                            src_path.path_link.push_back(src_snap.link);
                        src_path.cost = path_cost;
                        src_path.delay = path_delay;
                        src_visited_[u] = true;
                        src_snap.stage = 1;
                        src_stack.push_back(src_snap);
                        total_conflict_num += src_snap.cnt;
                        for (Link *link : egress_links)
                        {
                            NodeId node_id = link->ter_id;
                            if (link->used)
                            {
                                continue;
                            }
                            if (src_visited_[node_id])
                            {
                                continue;
                            }
                            Snapshot snap;
                            snap.node = node_id;
                            snap.delay = link->delay;

                            snap.cost = link->cost;
                            snap.stage = 0;
                            snap.link = link;
                            snap.cnt = find_link_in_conflict_path(snap.link);
                            src_stack.push_back(snap);
                        }
                    }
                }
            }
        }
    }
    int x = 5;
    std::cout << "Total number of iterations: " << num_iterations << "\n";
}

Link *SrlgPulse::check_conflict(const Path &ap_path, Path &bp_path)
{
    for (int i = 0; i < bp_path.path_link.size(); ++i)
    {
        for (Link *ap_link : ap_path.path_link)
        {
            if (ap_link->link_id == bp_path.path_link[i]->link_id)
            {
                if (ap_link->cousin.size() != 0)
                {
                    bp_path.path_link[i] = ap_link->cousin[0];
                    continue;
                }
                conflict_set_.path_link.push_back(ap_link);
                return ap_link;
            }
        }
    }
    return nullptr;
}

// void SrlgPulse::change_ap_link_seq(const Path &ap_path)
// {
//     for (Link *link : ap_path.path_link)
//     {
//         int loc = -1;
//         int egress_size = graph_->GetEgressLinks(link->source_id).size();
//         for (int i = 0; i < egress_size; ++i)
//         {
//             Link *tmp = graph_->GetEgressLinks(link->source_id)[i];
//             if (graph_->GetEgressLinks(link->source_id)[i]->link_id == link->link_id)
//             {
//                 loc = i;
//                 break;
//             }
//         }
//         if(loc != 0)
//             graph_->swap_link_loc(graph_->GetEgressLinks(link->source_id)[loc], graph_->GetEgressLinks(link->source_id)[0]);
//     }
// }

Path SrlgPulse::BPDfs(const Path &ap_path)
{
    struct Snapshot
    {
        Link *link;
        NodeId node;
        double cost;
        double delay;
        int stage;
        int cnt;
    };
    std::vector<Snapshot> src_stack;
    src_stack.reserve(1000000);
    Path src_path;
    src_path.path_info = {};
    src_path.path_link = {};
    src_path.cost = 0;
    src_path.delay = 0;
    Snapshot snapshot;
    snapshot.node = flow_.from;
    snapshot.cost = 0;
    snapshot.delay = 0;
    snapshot.stage = 0;
    snapshot.link = nullptr;
    src_stack.push_back(snapshot);
    int num_iterations = 0;
    Path bp;
    int total_conflict_num = 0;
    bool contain_conflict_link = false;
    Link *conflict_link = nullptr;
    while (!src_stack.empty())
    {
        ++num_iterations;
        Snapshot src_snap = src_stack.back();
        src_stack.pop_back();
        NodeId u = src_snap.node;
        if (contain_conflict_link || src_snap.stage == 1)
        {
            if (conflict_link != nullptr && src_snap.link->link_id == conflict_link->link_id)
            {
                contain_conflict_link = false;
                conflict_link = nullptr;
                src_path.path_info.pop_back();
                src_path.cost -= src_snap.cost;
                src_path.delay -= src_snap.delay;
                total_conflict_num -= src_snap.cnt;
                bp_visited_[u] = false;
                src_path.path_link.pop_back();
                src_stack.back().stage = 0;
            }
            else if (src_snap.stage == 1)
            {
                src_path.path_info.pop_back();
                src_path.path_link.pop_back();
                src_path.cost -= src_snap.cost;
                src_path.delay -= src_snap.delay;
                total_conflict_num -= src_snap.cnt;
                bp_visited_[u] = false;
            }
        }
        else
        {
            double path_cost = src_path.cost + src_snap.cost;
            double path_delay = src_path.delay + src_snap.delay;
            if (u == flow_.to)
            {
                src_path.Print();
                if (path_delay <= flow_.delay_ub &&
                    path_delay >= flow_.delay_lb)
                {
                    conflict_link = check_conflict(ap_path, src_path);
                    if (conflict_link == nullptr)
                    {
                        bp = src_path;
                        bp.cost = path_cost;
                        bp.delay = path_delay;
                        bp.path_link.push_back(src_snap.link);
                        bp.path_info.push_back(u);
                        // bp.Print();
                        return bp;
                    }
                    else
                    {
                        //    conflict_set_.path_link.push_back(conflict_link);
                        contain_conflict_link = true;
                    }
                }
            }
            else
            {
                // prune
                if (dst_delay_map_[u] + path_delay <= flow_.delay_ub &&
                    (accurate_ || updateSrcPath(u, path_cost, path_delay)))
                {
                    const std::vector<Link *> &egress_links =
                        graph_->GetBpEgressLinks(u);
                    if (!egress_links.empty())
                    {
                        src_path.path_info.push_back(u);
                        if (src_snap.link != nullptr && !find_link_in_conflict_path(src_snap.link))
                            src_path.path_link.push_back(src_snap.link);
                        src_path.cost = path_cost;
                        src_path.delay = path_delay;
                        bp_visited_[u] = true;
                        src_snap.stage = 1;
                        src_stack.push_back(src_snap);
                        for (Link *link : egress_links)
                        {
                            NodeId node_id = link->ter_id;
                            // if (link->used)
                            // {
                            //     continue;
                            // }
                            if (bp_visited_[node_id])
                            {
                                continue;
                            }
                            Snapshot snap;
                            snap.node = node_id;
                            snap.delay = link->delay;
                            snap.cost = link->cost;
                            snap.stage = 0;
                            snap.link = link;
                            src_stack.push_back(snap);
                        }
                    }
                }
            }
        }
    }
    // std::cout << "Total number of iterations: " << num_iterations << "\n";
    return bp;
}

void SrlgPulse::print() const
{
    std::cout << "\nTime(ms)  Optimality\n";
    std::pair<double, double> best_res_in_20ms;
    for (const std::pair<double, double> &time_cost : time_ms_cost_pairs_)
    {
        double optimality = static_cast<double>(total_cost_) / time_cost.second;
        if (time_cost.first < 20)
            best_res_in_20ms = time_cost;
        if (optimality > 0.8)
        {
            std::cout << time_cost.first << "   " << optimality << std::endl;
        }
    }
    double optimality = static_cast<double>(total_cost_) / best_res_in_20ms.second;
    std::cout << "Best Result In 20(ms):  Time: " << best_res_in_20ms.first << " (ms)  Optimality: " << optimality << std::endl;
}

void SrlgPulse::RemoveUsedNodes(const Path &path)
{
    for (int i = 0; i < num_nodes_; ++i)
    {
        bp_visited_[i] = false;
    }
    // for (int i = 1; i < path.path_info.size(); ++i)
    // {
    //     bp_visited_[path.path_info[i]] = true;
    // }
}

void SrlgPulse::RemoveUsedLinks(const Path &path)
{
    for (int i = 0; i < num_nodes_; ++i)
    {
        bp_visited_[i] = false;
    }
    //     for (Link *link : path.path_link)
    // {
    //     if (link->srlgs.size() == 0)
    //         continue;
    //     for (int srlg_id : link->srlgs)
    //     {
    //         graph_->ChangeLinkStatus(srlg_id, false);
    //     }
    // }
    // for (Link *link : path.path_link)
    // {
    //     link->used = true;
    // }
}

void SrlgPulse::RetrieveUsedLinks(const Path &path)
{
    for (Link *link : path.path_link)
    {
        link->used = false;
    }
}

void SrlgPulse::RemoveUsedSrlgs(const Path &path)
{
    for (int i = 0; i < num_nodes_; ++i)
    {
        bp_visited_[i] = false;
    }
}

void SrlgPulse::RetrieveUsedSrlgs(const Path &path)
{
    // for (Link *link : path.path_link)
    // {
    //     if (link->srlgs.size() == 0)
    //         continue;
    //     for (int srlg_id : link->srlgs)
    //     {
    //         graph_->ChangeLinkStatus(srlg_id, false);
    //     }
    // }
}

Path SrlgPulse::NodeSep(const Path &path)
{
    RemoveUsedNodes(path);
    graph_->update_bp_egress_links(path);
    flow_.delay_lb = path.delay - flow_.diff > flow_.delay_lb ? path.delay - flow_.diff : flow_.delay_lb;
    flow_.delay_ub = path.delay + flow_.diff < flow_.delay_ub ? path.delay + flow_.diff : flow_.delay_ub;

    return BPDfs(path);
}

Path SrlgPulse::LinkSep(const Path &path)
{
    RemoveUsedLinks(path);
    graph_->update_bp_egress_links(path);

    flow_.delay_lb = path.delay - flow_.diff > flow_.delay_lb ? path.delay - flow_.diff : flow_.delay_lb;
    flow_.delay_ub = path.delay + flow_.diff < flow_.delay_ub ? path.delay + flow_.diff : flow_.delay_ub;
    Path bp_res = BPDfs(path);
    RetrieveUsedLinks(path);
    return bp_res;
}

Path SrlgPulse::SrlgSep(const Path &path)
{
    RemoveUsedSrlgs(path);
    flow_.delay_lb = path.delay - flow_.diff > flow_.delay_lb ? path.delay - flow_.diff : flow_.delay_lb;
    flow_.delay_ub = path.delay + flow_.diff < flow_.delay_ub ? path.delay + flow_.diff : flow_.delay_ub;
    int ter = flow_.to;
    bool flag = false;
    for (Link *link : graph_->GetIngressLinks(ter))
    {
        if (!link->used)
        {
            flag = true;
            break;
        }
    }
    Path bp_res;
    if (flag)
    {
        bp_res = BPDfs(path);
    }
    else
        bp_res.delay = path.path_info.back();
    RetrieveUsedSrlgs(path);
    return bp_res;
}
